This invention relates to a method and apparatus for managing a memory, especially Non-Volatile Memory (NVM), for example Electrically Erasable Programmable Read Only Memory (EEPROM) or Flash Memory.
In multi-application devices, for example, in smartcards, several different applications, that is, independent software programs, are generally loaded into its NVM. During the life of a smartcard, applications may frequently be added and/or deleted from the memory. Since each application requires a contiguous address space, of memory blocks, in the memory, but different applications will be of different sizes, the deletion and addition of applications leaves small free spaces (often called holes) in the address space. This is called fragmentation of memory.
Fragmentation of memory results in poor utilisation of memory. Sometimes, it may not be possible to load a new application, even if its size is less than the sum of all the free spaces, since an application can only be loaded if its size is smaller than the largest available contiguous free space.
A number of ways to reduce fragmentation of memory are known. Several schemes are known to try to reduce fragmentation by loading new applications into the memory in particular ways. For example, a new application can be loaded into the smallest available free contiguous space that is large enough to hold the application (this is known as the xe2x80x9cbest fitxe2x80x9d method). This method leaves small chunks of memory that are often unusable because they are too small for any application, but can still add up to a sizable amount of memory when there are a large number of such small chunks. Alternatively, a new application can be loaded into the largest available free space, thereby leaving larger, possibly usable, chunks (this is known as the xe2x80x9cworst fitxe2x80x9d method), or can be loaded into the next (second) available space (known as the xe2x80x9cnext fitxe2x80x9d method). Other schemes are also known.
None of the schemes, however, solve the problem of loading an application where none of the free chunks of memory are sufficiently large for the new application, even when, overall, the free memory space is more than sufficient for the application. It is known to compact memory by moving all the applications together so as to be adjacent each other. However, if there is a power failure during the compaction process, some information may be lost. The problem can be mitigated by storing information being moved in a back-up buffer, but, in some devices such as smart cards, there is a limited amount of memory available and consequently back-ups may not be possible. Furthermore, even if the memory is available, the backing-up scheme requires more time to carry out.
Furthermore, when multiple applications are stored on a smartcard, it is sometimes necessary to have runtime-enforced mechanisms (sometimes called xe2x80x9cfirewallsxe2x80x9d) to isolate one application from another. In this environment, isolation means that one application cannot access data of another application, unless that other application explicitly provides an interface for such access. These separate protected data spaces are called xe2x80x9ccontextsxe2x80x9d
In general, each application defines a separate context. However, in some cases, for example with a smartcard running Java(trademark) script, such as the Java Card(trademark), more than one application can be contained in a single group, so that all the applications in the group share the same context. During the lifetime of the card, new applications can be created or deleted in the group, so that the size of the group context can vary. This is also true in the case of a context belonging to a single application because the size of the application can vary due to the creation and/or deletion of objects. Thus, providing a fixed allocation of memory for the context is either inefficient in use of memory or restrictive in creation of new applications or objects.
The present invention therefore seeks to provide a method and apparatus for managing a memory which overcomes, or at least reduces the above-mentioned problems of the prior art.
Accordingly, in one aspect, the invention provides a method of managing a memory having a plurality of memory blocks, the method comprising the steps of allocating the memory using logical addresses corresponding to memory blocks, mapping allocated memory blocks to allocated logical addresses, changing the allocation of the logical addresses so as to reduce numbers of unallocated logical addresses between allocated logical addresses, and updating the mapping when the allocation of at least one logical address has been changed.
In a preferred embodiment, the step of changing the allocation of the logical addresses is implemented so as to maximise the contiguity of unallocated logical addresses. Preferably, the step of changing the allocation of the logical addresses comprises moving unallocated logical addresses closer together in a logical address space. Conveniently, the memory is a Non Volatile Memory, for example in a smartcard.
Preferably, the method further comprises the step of initialising mapping of logical addresses to memory blocks, before the step of allocating the memory. The step of initialising preferably comprises randomly mapping the logical addresses to memory blocks.
In one embodiment, the method further comprises the step of accessing an allocated memory block by receiving an address command including a logical address, translating the logical address to the corresponding memory block and accessing the corresponding memory block.
Accordingly, in a second aspect, the invention provides a method of managing a memory having a plurality of memory blocks, the memory having a plurality of applications stored therein, at least one of the applications having a context, the method comprising the steps of allocating the memory using logical addresses corresponding to memory blocks such that the context of an application has contiguous logical addresses, mapping allocated memory blocks to allocated logical addresses, changing the size of at least one context, changing the allocation of the logical addresses so as to maximise the contiguity of logical addresses allocated to the at least one context, and updating the mapping when the allocation of at least one logical address has been changed.
In a preferred embodiment, the step of changing the allocation of the logical addresses comprises moving allocated logical addresses closer together in a logical address space. Conveniently, the memory is a Non Volatile Memory, for example in a smartcard.
Preferably, the method further comprises the step of initialising mapping of logical addresses to memory blocks, before the step of allocating the memory. The step of initialising preferably comprises randomly mapping the logical addresses to memory blocks.
In one embodiment, the method further comprises the step of accessing an allocated memory block by receiving an address command including a logical address, translating the logical address to the corresponding memory block and accessing the corresponding memory block.
According to a third aspect, the invention provides a memory management circuit comprising an input terminal, an address decoder coupled to the input terminal, an address table coupled to the address decoder, the address table having an output for providing a translation of logical addresses to blocks in a memory, and a controller coupled to the address table to change which logical addresses translate to which memory blocks.
In one embodiment, the controller changes which logical addresses translate to which memory blocks so as to reduce numbers of unallocated logical addresses between allocated logical addresses.
In a second embodiment, the controller changes which logical addresses translate to which memory blocks so as to maximise the contiguity of logical addresses allocated to at least one context stored in the memory.
Preferably, the address table comprises a plurality of latches.
In a preferred embodiment, the memory management circuit further comprising a combining circuit coupled to the input terminal and to the output of the address table for combining at least part of a logical address received at the input terminal with the translation of at least part of the logical address provided by the address table.